#include "movingCount.h"
int bitSum(int a) {
    int res = 0;
    while (a > 0) {
        res += a % 10;
        a /= 10;
    }
    return res;
}

int movingCount(int m, int n, int k) {
    if (!k)
        return 1;

    vector<vector<int>> visited(m, vector<int>(n, 0));
    int res = 0;
    for (int r = 0; r < m; r++) {
        for (int c = 0; c < n; c++) {
            if (r == 0 && c == 0) {
                res = 1;
                visited[r][c] = 1;
                continue;
            }
            if (bitSum(r) + bitSum(c) > k)
                continue;
            else {
                if (r - 1 >= 0)
                    visited[r][c] |= visited[r - 1][c];
                if (c - 1 >= 0)
                    visited[r][c] |= visited[r][c - 1];
                res += visited[r][c];
            }
        }
    }
    return res;
}

int movingCountDfs(int r, int c, int m, int n, int k,
                   vector<vector<bool>> &visited) {
    if (r < 0 || r >= m || c < 0 || c >= n || bitSum(r) + bitSum(c) > k ||
        visited[r][c]) {
        return 0;
    } else {
        visited[r][c] = true;
        return 1 + movingCountDfs(r + 1, c, m, n, k, visited) +
               movingCountDfs(r - 1, c, m, n, k, visited) +
               movingCountDfs(r, c + 1, m, n, k, visited) +
               movingCountDfs(r, c - 1, m, n, k, visited);
    }
}
int movingCountDfs(int m, int n, int k) {
    vector<vector<bool>> visited =
        vector<vector<bool>>(m, vector<bool>(n, false));
    return movingCountDfs(0, 0, m, n, k, visited);
}
